1. Field of the Invention
This invention relates to compilers and instruction scheduling, and particularly to for implementing shadow versioning to improve data dependence analysis for instruction scheduling.
2. Description of Background
In a program, when an instruction writes to a piece of data that is also accessed by another instruction, we say there is data dependence between the two instructions or the two data accesses. Data dependence must be carefully preserved in compiler optimizations to maintain correct program semantics. The quality of data dependence information has big impacts on compiler optimizations because data dependence information is needed in many optimizations, especially in instruction scheduling. In the following code snippet, it appears that array A is accessed twice in the loop body.
Line 1: int A[2000], i;Line 2: for (i=0; i<1000; i++) {Line 3:  A[i] = i;Line 4:  A[i+1000] = 3*i;Line 5: }
Lines 3 and line 4 must be executed sequentially because the same piece of data (array A) is accessed one after the other. However, the two accesses to the array A don't overlap in each iteration. If a compiler figures out this fine-grained data dependence relationship, it could schedule the instructions at line 3 and line 4 to be executed in parallel, improving runtime performance.
A shadow symbol represents a set of memory locations that are accessed by certain pointer dereferences or array indexing. Without sophisticated analysis, a compiler must conservatively assume that two accesses to the same shadow symbol refer to the same memory location.
Compilers have abundant supporting information to get better dependence information in the high-level optimizer. Unfortunately, the information collected in high-level optimizations is difficult to be transferred to instruction scheduling because code keeps changing during compilation and the task of bookkeeping the data dependence information during compilation is very complex, if not impossible.
What is needed is a way to take advantage of the analysis results in high-level optimizations of a compiler to get better data dependence information for shadows in the low-level optimizer.